#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-10 9:46 上午
# @Author  : yangdy
# @File    : 2020-09-10.40.组合总和II
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        if not candidates or target <= 0:
            return ans
        n = len(candidates)
        candidates.sort()
        nums = []
        x = 0
        for i in range(1, n):
            if candidates[i] != candidates[i-1]:
                nums.append((candidates[i-1], i-x))
                x = i
        nums.append((candidates[n-1], n-x))
        ln = len(nums)

        def dfs(ii, nn, tt, ns):
            if ii >= nn or tt <= 0:
                return
            for j in range(nums[ii][1]+1):
                if j * nums[ii][0] == tt:
                    ans.append(ns+[nums[ii][0]]*j)
                elif j * nums[ii][0] < tt:
                    dfs(ii+1, nn, tt - j * nums[ii][0], ns + [nums[ii][0]] * j)
                else:
                    break
        dfs(0, ln, target, [])
        return ans


questions = [
    ([10, 1, 2, 7, 6, 1, 5], 8),
    ([2, 5, 2, 1, 2], 5),
]

work(questions, lambda q: Solution().combinationSum2(q[0], q[1]))
